/*
day156_3
2020.1.31
*/ 
#include<iostream>
#include<vector>
using namespace std;

class Solution1 {
public:
    int maxProfit(vector<int>& prices) {
    	if(prices.empty()) return 0;
    	
    	int size=prices.size();
        vector<int> vec_max(size);
        vector<int> vec_min(size);
        
        int max=prices[size-1];
        vec_max[size-1]=prices[size-1];
        for(int i=size-2;i>=0;--i)
        {
        	max = max>=prices[i] ? max : prices[i];
        	vec_max[i]=max;
		}
		
		
		int min=prices[0];
		vec_min[0]=prices[0];
        for(int i=1;i<size;i++)
        {
        	min = min<=prices[i] ? min : prices[i];
        	vec_min[i]=min;
		}
		
		
		int res=0;
		for(int i=0;i<size;i++)
		{
			int cur=vec_max[i]-vec_min[i];
			res=res>=cur ? res : cur;
		}
		
		return res;
    }
};


class Solution2 {
public:
    int maxProfit(vector<int>& prices) {
        int minprice=INT_MAX;
        int maxpro=0;
        
        for(int i=0;i<prices.size();++i)
        {
        	if(prices[i]<minprice)
        	{
        		minprice=prices[i];
        		continue;
			}
			int curpro=prices[i]-minprice;
			maxpro=maxpro > curpro ? maxpro : curpro;
		}
		return maxpro;
    }
};
int main()
{
	return 0;
}
